import java.util.*;
public class Solution {

    ArrayList<String> ret = new ArrayList<>();
    Set<String> set = new HashSet<>();
    StringBuilder temp = new StringBuilder();
    int[] visited;

    public void dfs(String s){

        for (int i = 0; i < s.length(); i++) {
            if (visited[i] == 0) {
                visited[i] = 1;
                temp.append(s.charAt(i));
                dfs(s);

                if (temp.length() == s.length())    {
                    set.add(temp.toString());
                }
                temp.delete(temp.length() - 1, temp.length());
                visited[i] = 0;
            }
            else {
                continue;
            }
        }
    }

    public ArrayList<String> Permutation(String str) {
        if (str == "" || str == null) 
            return ret;

        int length = str.length();
       
        visited = new int[length];
        Arrays.fill(visited, 0);

        dfs(str);

        for (String i: set) {
            ret.add(i);
        }

        return ret;

    }
}